package binarytree

func hasPathSum(root *TreeNode, targetSum int) bool {

	if root == nil {
		return false
	}
	var helper func(root *TreeNode, targetSum int) bool
	helper = func(root *TreeNode, targetSum int) bool {
		if root.Left == nil && root.Right == nil {
			return root.Val == targetSum
		}
		left, right := false, false
		if root.Left != nil {
			left = helper(root.Left, targetSum-root.Val)
		}
		if root.Right != nil {
			right = helper(root.Right, targetSum-root.Val)
		}
		return left || right
	}

	return helper(root, targetSum)
}

func hasPathSum2(root *TreeNode, targetSum int) bool {

	if root == nil {
		return false
	}

	stack := []*TreeNode{root}
	sums := []int{0}

	for len(stack) != 0 {
		node := stack[len(stack)-1]
		sum := sums[len(sums)-1]
		stack = stack[:len(stack)-1]
		sums = sums[:len(sums)-1]

		if node.Left == nil && node.Right == nil && targetSum-sum == root.Val {
			return true
		}

		if root.Right != nil {
			stack = append(stack, root.Right)
			sums = append(sums, sum+root.Val)
		}
		if root.Left != nil {
			stack = append(stack, root.Left)
			sums = append(sums, sum+root.Val)
		}
	}
	return false
}
